With aggressive technology scaling, the accurate and efficient modeling and simulation of interconnect effects has become (and continues to be) a problem of central importance. In a three-dimensional interconnect structure there can be significant amounts of coupling, both inductive and capacitive, between interconnects. Models that capture these effects tend to involve large matrices, resulting in extraordinary demands on memory. Simulation with these models require prohibitive amounts of computation.
While all coupling effects in theory extend without bound, it is well-recognized that, in practice, the effects of capacitive coupling, and to some extent that of inductive coupling, can be assumed to be local without much sacrifice in accuracy. Practical modeling and simulation techniques exploit this localization to significantly reduce storage and computational costs. For practical interconnect structures, the capacitance matrix C and the inverse of the inductance matrix K=L−1 turn out to be (approximately) sparse. A number of techniques exploit the sparsity in K at extraction level. Exploiting sparsity of C and K in simulation however, is much less straightforward. The main problem is that simulation requires terms that not only involve the sparsified matrices C and K, but also inverses of terms that involve them; these inverses are dense in general.
The Modified Nodal Analysis (MNA) of interconnect structures such as the one shown in FIG. 1 yields equations of the form{tilde over (G)}x+{tilde over (C)}{dot over (x)}=b,   (1)where
            G      ~        =          [                                                                                  A              l              T                                                                          -                              A                l                                                          0                              ]        ,            C      ~        =          [                                                                    0                                                0                                L                              ]        ,      x    =          [                                                  v              n                                                                          i              l                                          ]        ,          ⁢      b    =          [                                                                  A                i                T                            ⁢                              I                s                                                                          0                              ]        ,          =                  A        g        T            ⁢              R                  -          1                    ⁢              A        g              ,          ⁢            and      ⁢                          ⁢              =                  A        c        T            ⁢                        CA          c                .            
R is the resistance matrix. The matrices , L and C are the conductance, inductance and capacitance matrices respectively, with corresponding adjacency matrices Ag, Al and Ac. Is is the current source vector with adjacency matrix Al, and vn and il are the node voltages and inductor currents respectively. With n denoting the number of inductors, we note thatL, C, R ∈ Rn×n, ,  ∈ R2n×2n.
A standard algorithm for the numerical integration of differential equations such as (1) is the trapezoidal method. Consider a uniform discretization of the time axis with resolution h. Then, using the notation Xk=x(kh), and the approximations
            ⅆ              ⅆ        t              ⁢          x      ⁡              (        t        )              ⁢      ❘          t      =      kh        ⁢      ≈                                        x                          k              +              1                                -                      x            k                          h            ⁢                          ⁢      and      ⁢                          ⁢              x        k              ≈                            x                      k            +            1                          +                  x          k                    2      over the interval [kh, (k+1)h], we may solve for xk+1 in terms of xk by solving the equation
                                          (                                                            G                  ~                                2                            +                                                C                  ~                                h                                      )                    ⁢                      x                          k              +              1                                      =                                            -                              (                                                                            G                      ~                                        2                                    -                                                            C                      ~                                        h                                                  )                                      ⁢                          x              k                                +                                                                      b                                      k                    +                    1                                                  +                                  b                  k                                            2                        .                                              (        2        )            A direct implementation of this algorithm requires O(n3+pn2) operations, where p is the number of time steps. The direct implementation ignores the structure of the matrices {tilde over (G)} and {tilde over (C)} that is evident in (1); explicitly recognizing this structure yields the so-called Nodal Analysis (NA) equations, used in INDUCTWISE:
                                                        (                                                                  ⁢                                                  +                                                      2                    h                                    ⁢                  C                                +                                                      h                    2                                    ⁢                  S                                            )                                      ︸              U                                ⁢                      v            n                          k              +              1                                      =                                                            (                                                      -                                                        +                                                            2                      h                                        ⁢                    C                                    -                                                            h                      2                                        ⁢                    S                                                  )                                            ︸                V                                      ⁢                          v              n              k                                -                      2            ⁢                          A              l              T                        ⁢                          i              l              k                                +                                                    A                i                T                            ⁡                              (                                                      I                    s                                          k                      +                      1                                                        +                                      I                    s                    k                                                  )                                      .                                              (        3        )            and2AlTilk+1=2AlTilk+hS(vnk+1+vnk),   (4)where S=AlKAlT (recall that K=L−1, L being the inductance matrix, with corresponding adjacency matrix Al, and AlT being the transpose of Al).
The NA equations (3) and (4) enjoy several advantages over the MNA equations (1). The first advantage is that the solution of equations (1), a problem of size 3n, has been divided into two sub-problems of sizes 2n and 2n, which yields computational savings with polynomial-time algorithms. Next, it has been observed that with typical VLSI interconnect structures, the matrices K, C and G exhibit sparsity. This can be used at the extraction stage to write down (3) and (4) with fewer parameters. Finally, at the simulation stage, the structure of the matrix U defined in (3)—symmetry, positive-definiteness and sparsity—lends itself to the use of fast and sound numerical techniques such as Cholesky factorizations. These advantages have been extensively used to develop INDUCTWISE. For future reference, we note that the computation with INDUCTWISE is O(n3+pn2) operations, and is usually dominated by O(pn2).